package Graph.graphWithNoweight.bfs;

import Graph.graphWithNoweight.dfs.Graph;

import java.util.HashSet;

//寻找割点
public class FindCutPoint {

    private Graph G;
    private boolean[] visited;

    private int ord[];
    private int low[];
    private int cnt;

    //每一个整形代表一个割点  这里选择 HashSet  因为它会帮我们判断重复
    private HashSet<Integer> res;

    public FindCutPoint(Graph G){

        this.G = G;
        visited = new boolean[G.V()];

        res = new HashSet<>();
        ord = new int[G.V()];
        low = new int[G.V()];
        cnt = 0;

        for(int v = 0; v < G.V(); v ++) {
            if(!visited[v]) {
                dfs(v, v);
            }
        }
    }

    private void dfs(int v, int parent){

        visited[v] = true;
        ord[v] = cnt;
        low[v] = ord[v];
        cnt ++;

        // 初始代表v这个节点有0个孩子节点。
        int child=0;
        for(int w: G.adj(v)) {
            if(!visited[w]){
                dfs(w, v);
                //到这一步，说明已经到了回归阶段。
                low[v] = Math.min(low[v], low[w]);
                //v!=parent 排除是根节点
                if(v!=parent && low[w] > ord[v]) {
                    res.add(v);
                }
                child++;
                //如果是一个环的 的，从根节点出来，变量会一口气遍历到底，child==1  不会大于1
                if(v==parent && child>1){
                    res.add(v);
                }
            }
            else if(w != parent) {
                low[v] = Math.min(low[v], low[w]);
            }
        }
    }

    public HashSet<Integer> result(){
        return res;
    }

    public static void main(String[] args){

        Graph g = new Graph("g.txt");
        FindCutPoint fb = new FindCutPoint(g);
        System.out.println("cutPoint in g : " + fb.result());

/*        Graph g2 = new Graph("g2.txt");
        FindCutPoint fb2 = new FindCutPoint(g2);
        System.out.println("Bridges in g2 : " + fb2.result());

        Graph g3 = new Graph("g3.txt");
        FindCutPoint fb3 = new FindCutPoint(g3);
        System.out.println("Bridges in g3 : " + fb3.result());

        Graph tree = new Graph("tree.txt");
        FindCutPoint fb_tree = new FindCutPoint(tree);
        System.out.println("Bridges in tree : " + fb_tree.result());*/
    }
}
